package com.zjsru.plan2023.oneday;

/**
 * @Author: cookLee
 * @Date: 2023-11-08
 * 最长平衡子字符串
 */
public class FindTheLongestBalancedSubstring {

    /**
     * 主
     * \
     * 输入：s = "01000111"
     * 输出：6
     * 解释：最长的平衡子字符串是 "000111" ，长度为 6 。
     * \
     * 输入：s = "00111"
     * 输出：4
     * 解释：最长的平衡子字符串是 "0011" ，长度为  4 。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        FindTheLongestBalancedSubstring findTheLongestBalancedSubstring = new FindTheLongestBalancedSubstring();
        String s = "01000111";
        System.out.println(findTheLongestBalancedSubstring.findTheLongestBalancedSubstring4(s));
    }

    /**
     * 查找最长平衡子字符串
     *
     * @param s s
     * @return int
     */
    public int findTheLongestBalancedSubstring(String s) {
        int left = 0;
        int ans = 0;
        int count0 = 0;
        int count1 = 0;
        while (left < s.length()) {
            if (s.charAt(left) == '0') {
                count0++;
                left++;
            } else {
                while (left < s.length() && s.charAt(left) == '1') {
                    count1++;
                    left++;
                    ans = Math.max(ans, Math.min(count0, count1) * 2);
                }
                count0 = 0;
                count1 = 0;
            }
        }
        return ans;
    }


    /**
     * 找到最长平衡子2:遍历寻找子串长度。两者取最小值*2，类似第一种做法的另一版本
     *
     * @param s s
     * @return int
     */
    public int findTheLongestBalancedSubstring2(String s) {
        int n = s.length(), idx = 0, ans = 0;
        while (idx < n) {
            int a = 0, b = 0;
            while (idx < n && s.charAt(idx) == '0' && ++a >= 0) {
                idx++;
            }
            while (idx < n && s.charAt(idx) == '1' && ++b >= 0) {
                idx++;
            }
            ans = Math.max(ans, Math.min(a, b) * 2);
        }
        return ans;
    }

    /**
     * 找到最长平衡子3:双指针
     *
     * @param s s
     * @return int
     */
    public int findTheLongestBalancedSubstring3(String s) {
        int n = s.length();
        int ans = 0;
        int i = 0;
        while (i < n - 1) {
            int left = i, right = i + 1;
            //找到01字串，以此为基础向外扩展 直到获得一个完整的字串 01 -> 0011 -> 000111
            while (left >= 0 && right < n && s.charAt(left) == '0' && s.charAt(right) == '1') {
                left--;
                right++;
            }
            ans = Math.max(ans, right - left - 1);
            //定位新的指针
            i = right;
        }
        return ans;
    }

    /**
     * 找到最长平衡子4:添加字符串组合直到不存在为止
     *
     * @param s s
     * @return int
     */
    public int findTheLongestBalancedSubstring4(String s) {
        int ans = 0;
        String str = "01";
        return this.helper(str, s, ans);
    }

    /**
     * 递归助手类
     *
     * @param str    str
     * @param origin 产地
     * @param ans    ans
     * @return {@link Integer}
     */
    private Integer helper(String str, String origin, int ans) {
        if (origin.contains(str)) {
            ans = Math.max(ans, str.length());
            str = "0" + str + "1";
            Integer helper = this.helper(str, origin, ans);
            return Math.max(helper, ans);
        }
        return ans;
    }

}
